package com.csdemos.algs.dynamic;

import com.csdemos.algs.BinaryTree;
import com.csdemos.algs.BinaryTree.Node;

public class BST {

	public static int[][] optimalBST(double[] p, double[] q, int n) {
		double[][] e = new double[n + 2][n + 2];
		double[][] w = new double[n + 2][n + 2];
		int[][] root = new int[n][n];
		int j;
		double t;
		for (int i = 1; i <= n + 1; i++) {
			e[i][i - 1] = q[i - 1];
			w[i][i - 1] = q[i - 1];
		}
		for (int l = 1; l <= n; l++) {
			for (int i = 1; i <= n - l + 1; i++) {
				j = i + l - 1;
				e[i][j] = Double.MAX_VALUE;
				w[i][j] = w[i][j - 1] + p[j - 1] + q[j];
				for (int r = i; r <= j; r++) {
					t = e[i][r - 1] + e[r+1][j] + w[i][j];
					if (t < e[i][j]) {
						e[i][j] = t;
						root[i - 1][j - 1] = r;
					}
				}
			}
		}
		return root;
	}
	
	public static BinaryTree constructOptimalBST(int[][] root, int[] keys) {
		BinaryTree tree = new BinaryTree();
		tree.setRoot(constructOptimalSubBST(root, keys, 1, root.length, new int[]{0}));
		return tree;
	}
	
	private static Node constructOptimalSubBST(int[][] root, int[] keys, int i, int j, int[] c) {
		int r = root[i - 1][j - 1];
		Node node = new Node(keys[r - 1]);
		if (i == j) {
			node.left = new Node(c[0]--);
			node.right = new Node(c[0]--);
		} else if (i == r) {
			node.left = new Node(c[0]--);
			node.right = constructOptimalSubBST(root, keys, r + 1, j, c);
		} else if (r == j) {
			node.left = constructOptimalSubBST(root, keys, i, r - 1, c);
			node.right = new Node(c[0]--);
		} else {
			node.left = constructOptimalSubBST(root, keys, i, r - 1, c);
			node.right = constructOptimalSubBST(root, keys, r + 1, j, c);
		}
		node.left.parent = node;
		node.right.parent = node;
		return node;
	}
	
	public static void main(String[] args) {
		int n = 5;
		int[] keys = new int[n];
		double[] p = new double[] {      0.15, 0.10, 0.05, 0.10, 0.2};
		double[] q = new double[] {0.05, 0.10, 0.05, 0.05, 0.05, 0.1};
		for (int i = 0; i < n; i++) {
			keys[i] = i + 1;
		}
		int[][] root = optimalBST(p, q, n);
		BinaryTree tree = constructOptimalBST(root, keys);
		System.out.println(tree.parenthesisTreeWalk(tree.getRoot()));
	}
}
